Memory devices are often used to store data provided by a computer program. Examples of memory storage devices include, but are not limited to, solid-state drives, hard disk drives, and optical drives. These types of storage devices are inexpensive and hold large amounts of data. However, one tradeoff for their economic value is that they are slow compared to other components used in a computer. For example, a consumer hard drive can store terabytes of data cheaply, but has a maximum theoretical transfer rate of 300 megabytes (MB) per second. Random access memory (RAM) is faster in performance but higher in price, with a maximum theoretical transfer rate of 12.8 gigabytes (GB) per second. A central processing unit (CPU) with specialized memory known as level 1 (L1) cache or level 2 (L2) cache has even better performance but at an even higher price, with a transfer rate of 16 GB per second, or over fifty times faster than the storage device.
Because computer components exhibit this tradeoff between price and performance, a technique known as caching may be used to increase, or accelerate, overall system performance. Caching may be used to store data requested from one slower component, into another faster component, to speed future requests for the same data. The data stored in a cache often may be values previously requested by a software application, by an operating system, or by another hardware component. Caching organizes a small amount of fast-access memory and a large amount of slow-access memory. The first time that a value is requested, the data is not in the cache, so the requested value is retrieved from the slow-access memory. In a cache, when the value is retrieved from the slow-access memory, the value is sent to the component that requested it, and the value also is stored in the fast-access memory for future requests. The next time that the same value is requested by the operating system or by any other program, the value is retrieved from the fast-access memory, with the result that the overall system performance is faster, or accelerated, by virtue of the value being available from the fast-access memory. By using faster memory components to cache data, the more requests that can be served from the cache instead of the slower storage device, and the faster the overall system performance.
A cache can be considered a type of hash table. A hash table refers to a computer data structure which stores a plurality of data in a collection, such as an array, using a numerical index. A hash function determines a numerical index, or location in the hash table to store the data, as a function of the input data to be stored. A cache is a type of hash table because a memory controller accepts, as input, data to be stored, and stores the data to a location in the cache according to an index determined based on the input data. Typically the data to be stored in a hash table or in a cache is referred to as a key. The key can include an original memory address or index of the contents, and the contents stored at that address, when caching contents of memory such as volatile RAM or persistent storage.